﻿// 堆排序.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<vector>
#include<functional>
#include<algorithm>
#include<queue>

using namespace std;

/// <summary>
/// 维护堆
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="parent"></param>
/// <param name="length"></param>
/// <param name="cmp"></param>
template<typename T,class Cmp_ = greater<T>>
void HeapAdjust(vector<T>& array, int parent, int length, Cmp_ cmp)
{
    T temp = array[parent];   //保存父节点
    int leftChild = parent * 2 + 1;
    int rightChild = parent * 2 + 2;

    //自上向下排查遍历
    while (leftChild<length)
    {
        int child = leftChild;
        // 如果有右孩子结点，并且右孩子结点的在堆比较中优于左节点结点，则选取右孩子结点
        if (rightChild < length && cmp(array[rightChild], array[leftChild]))
            child = rightChild;

        // 如果父结点的值在堆比较中优于孩子结点的值，则直接跳出循环
        if (cmp(temp, array[child]))
            break;

        //把孩子结点的值赋给父结点
        array[parent] = array[child];

        //选取子结点的左孩子结点，继续向下筛选
        parent = child;
        leftChild = parent * 2 + 1;
        rightChild = parent * 2 + 2;
    }

    array[parent] = temp;
}

/// <summary>
/// 堆排序
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
/// <param name="cmp"></param>
template<typename T,class Cmp_ = greater<T>>
void HeapSort(vector<T>& array,Cmp_ cmp)
{
    //循环建立初始堆（自下向上不断维护）
    for (int parent = array.size()/2-1; parent >=0; parent--)
    {
        HeapAdjust(array, parent, array.size(), cmp);
    }

    for (int i = array.size()-1; i>0; i--)
    {
        //最后第一个元素和待维护堆的最后一个元素(i)交换
        swap(array[0],array[i]);

        //继续维护0~i-1索引的堆
        HeapAdjust(array, 0, i, cmp);
    }
}

int main()
{
    vector<int> arr = { 9,8,5,3,4,1,2,7,6 };
    auto cmp = [](const int& x, const int& y)->bool
    {
        return x > y;
    };
    HeapSort(arr,less<>());
    std::cout << "Hello World!\n";
}
// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
